//
// Created by hay boy on 2022/7/26.
//

#ifndef ALGORITHMS_HUFFMANTREE_H
#define ALGORITHMS_HUFFMANTREE_H

#include "../tree/binaryTree/linkedBinaryTree.h"
#include "../priorityQueue/minHeap.h"

template<class T>
struct huffmanNode {
    linkedBinaryTree<int> *tree;
    T weight;
    explicit operator T() const{
        return weight;
    }
};
template<class T>
linkedBinaryTree<int> *huffmanTree(T weight[], int n) {
    huffmanNode<T>* hNode = new huffmanNode<T>[n+1];
    linkedBinaryTree<int> emptyTree;
    for(int i = 0;i<=n;i++){
        hNode[i].weight = weight[i];
        hNode[i].tree = new linkedBinaryTree<int>;
        hNode[i].tree->makeTree(i,emptyTree,emptyTree);
    }
    minHeap<huffmanNode<T>> heap(1);
    heap.initialize(hNode,n);
    huffmanNode<T> w,x,y;
    linkedBinaryTree<int> *z;
    for(int i = 1;i<n;i++){
        x = heap.top();
        heap.pop();
        y = heap.top();
        heap.pop();
        z = new linkedBinaryTree<int>;
        z->makeTree(0,*x.tree,*y.tree);
        w.weight = x.weight+y.weight;
        w.tree = z;
        heap.push(w);
        delete x.tree;
        delete y.tree;
    }
    return heap.top().tree;
}
#endif //ALGORITHMS_HUFFMANTREE_H
